package com.leetcode.BinaryTree;

import java.util.ArrayList;
import java.util.List;

//二叉树的层序遍历
public class lc_102 {
    public static void main(String[] args) {

    }

    //定义全局变量
    //1.判断:需要维护全局变量,可以直接定义出来,也可以直接传入方法
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        bfs(root, 0);
        return result;
    }

    /**
     * 2.返回参数:下层不需要给上层返回东西,而是一起维护一个全局变量result
     *
     * @param root  当前结点
     * @param level 当前结点所在的层
     */
    private void bfs(TreeNode root, int level) {
        //3.边界条件:结点为空,直接返回
        if (root == null) {
            return;
        }
        //4.每层逻辑 :
        //4.1.如果当前层对于列表还未创建,则创建该列表
        if (result.size() == level) {
            result.add(new ArrayList<>());
        }
        //4.2.将当前结点的值添加到对应层的列表中
        result.get(level).add(root.val);
        //4.3.递归处理左子结点,层信息+1
        bfs(root.left, level + 1);
        //4.4.递归处理右子结点,层信息+1
        bfs(root.right, level + 1);
    }
}
